# -*- coding: utf-8 -*-

"""剑指 Offer II 008. 和大于等于 target 的最短子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：
1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5"""


class Solution:
    def minSubArrayLen_low(self, target: int, nums) -> int:
        """滑动窗口+二分查找，此效率低，二分查找时大量求和计算"""
        def bin_search(head, tail):
            new_tail = (head+tail)//2
            while True:
                if tail-new_tail <= 1:
                    if sum(nums[head:new_tail]) >= target:
                        return new_tail-1
                    elif sum(nums[head:new_tail+1]) >= target:
                        return new_tail
                    else:
                        return tail

                if sum(nums[head:new_tail+1]) >= target:
                    tail = new_tail
                    new_tail = (head+new_tail)//2
                else:
                    new_tail = (new_tail+tail)//2
        
        if sum(nums) < target:
            return 0

        ln = len(nums)
        
        anchor = 0
        window = nums
        window_ln = ln
        while True:
            if anchor == ln:
                break

            if sum(nums[anchor : anchor+window_ln]) >= target:
                head, tail = anchor, ln-1 if anchor+window_ln>=ln else anchor+window_ln-1
                new_window_tail = bin_search(head, tail)
                window = nums[anchor: new_window_tail+1]
                window_ln = new_window_tail-anchor+1

            anchor += 1
        
        return window_ln
    
    def minSubArrayLen_normal(self, target, nums):
        """借鉴题解，前缀和+二分查找"""
        def bin_search(head, tail):
            if tail - head <= 1:
                if psums[head] >= oppo_target:
                    return head
                elif psums[tail] >= oppo_target:
                    return tail
                else:
                    return

            middle = (head + tail) // 2
            if psums[middle] > oppo_target:
                head, tail = head, middle
            elif psums[middle] < oppo_target:
                head, tail = middle, tail
            else:
                return middle

            return bin_search(head, tail)

        if sum(nums) < target:
            return 0
        
        psums = [0]
        for n in nums:
            psums.append(psums[-1]+n)

        tail = len(psums)-1
        window = tail
        for i in range(1, len(psums)):
            oppo_target = psums[i-1]+target
            end = bin_search(i, tail)
            if end and (ln:=end-i+1) < window:
                window = ln
        
        return window

    def minSubArrayLen(self, target, nums):
        """借鉴题解：滑动窗口，双指针"""
        if sum(nums) < target:
            return 0
        
        start, end = 0, 0
        last = len(nums)-1
        window = last+1
        total = nums[0]
        while True:
            if start > last:
                break
            if total < target:
                if end == last:
                    break
                else:
                    end += 1
                    total += nums[end]
            else:
                ln = end-start+1
                if ln < window:
                    window = ln
                total -= nums[start]
                start += 1
        
        return window


if __name__ == '__main__':
    so = Solution()
    print(so.minSubArrayLen(7, [2,3,1,2,4,3]))
    print(so.minSubArrayLen(4, [1,4,4]))
    print(so.minSubArrayLen(11, [1,1,1,1,1,1,1,1]))
    print(so.minSubArrayLen(6, [10,2,3,]))
